﻿/*
题目：优质数对的总数

给你两个整数数组 nums1 和 nums2，长度分别为 n 和 m。同时给你一个正整数 k。

如果 nums1[i] 可以被 nums2[j] * k 整除，则称数对 (i, j) 为 优质数对（0 <= i <= n - 1, 0 <= j <= m - 1）。

返回 优质数对 的总数。
*/

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include "TreeNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>
#include <list>
#include <numeric>

using namespace std;

class Solution {
public:
    // nums[i] 可以 % (nums[j] * k)
    // 也就是 nums[i] 存在是 (nums[j] * k) 的倍数
    long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        unordered_map<int, int> record;
        int nums1_max = nums1[0];
        for (int e : nums1) {
            record[e]++;
            nums1_max = max(nums1_max, e);
        }

        unordered_map<int, int> elem2num;
        for (int e : nums2) {
            elem2num[e]++;
        }

        long long res = 0L;
        for (const auto& kv : elem2num) {
            int base = kv.first * k;
            for (int i = 1; i * (long long)base <= nums1_max; i++) {
                if (record.count(i * base)) {
                    res += (long long)record[i * base] * kv.second;
                }
            }
        }

        return res;
    }
};